home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_100 / 172_01 / dfa.c < prev    next >
Text File  |  1980-01-01  |  10KB  |  346 lines
  1. /*
  2.   HEADER: CUG     nnn.nn;
  3.   TITLE:     LEX - A Lexical Analyser Generator
  4.   VERSION:     1.0 for IBM-PC
  5.   DATE:      Jan 30, 1985
  6.   DESCRIPTION:     A Lexical Analyser Generator. From UNIX
  7.   KEYWORDS:     Lexical Analyser Generator YACC C PREP
  8.   SYSTEM:     IBM-PC and Compatiables
  9.   FILENAME:      DFA.C
  10.   WARNINGS:     This program is not for the casual user. It will
  11.          be useful primarily to expert developers.
  12.   CRC:         N/A
  13.   SEE-ALSO:     YACC and PREP
  14.   AUTHORS:     Scott Guthery 11100 leafwood lane Austin, TX 78750
  15.   COMPILERS:     DESMET-C
  16.   REFERENCES:     UNIX Systems Manuals
  17. */
  18. /*
  19.  * Copyright (c) 1978 Charles H. Forsyth
  20.  *
  21.  * Modified 02-Dec-80 Bob Denny -- Conditionalize debug code for reduced size
  22.  * Modified 29-May-81 Bob Denny -- Clean up overlay stuff for RSX.
  23.  * More     19-Mar-82 Bob Denny -- New C library & compiler
  24.  * More     03-May-82 Bob Denny -- Final touches, remove unreferenced autos
  25.  * More     29-Aug-82 Bob Denny -- Clean up -d printouts
  26.  * More     29-Aug-82 Bob Denny -- Reformat for readability and comment
  27.  *                                 while learning about LEX.
  28.  * More        20-Nov-83 Scott Guthery -- Adapt for IBM PC & DeSmet C
  29.  *
  30.  * Modified 22-Jun-86 Andrew Ward -- Modified code to compile under Lattice C 
  31.  *                     version 3.0h.  Corrected several errors
  32.  *                 from the assumption that pointers and
  33.  *                 integers are the same size.     
  34.  */
  35.  
  36. /*
  37. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
  38. ::::::::             Start of Procedure: DFA                         :::::::::
  39. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
  40. */
  41.  
  42. #include <stdio.h>
  43. #include "lexlex.h"
  44.  
  45. #define PAGE(title)
  46.  
  47. #ifdef LATTICE
  48. /* Lattice headers */
  49. #include <assert.h>
  50. #include <string.h>
  51. #include <stdlib.h>
  52. /* argument typed functions */
  53. extern char        *lalloc(unsigned, unsigned, char *);
  54. extern struct set  *newset(struct nfa **, int, int);
  55. extern struct set  *eclosure(struct set *);          /* Used only by DFA */
  56. extern struct dfa  *defalt(struct dfa *,struct xset **);/* Used only by DFA */
  57. extern struct dfa  *newdfa();  /* --> current DFA state */
  58. extern struct move *stbase(struct xset *);           /* Used only by DFA */
  59. extern struct xset *addxset( int, struct xset *);
  60. extern struct xset *addset(struct nfa *, struct xset *);
  61. extern void        add(struct nfa **, struct nfa ***, struct nfa *);
  62. extern void        error( char *, char * );
  63. extern void        f_error( char *, char * );
  64. extern void        setbase(struct dfa *, struct move *, struct xset *);
  65.  
  66. #else
  67.  
  68. /* Use if not Lattice C or not lint */
  69. #define void int
  70.  
  71. extern struct set  *newset();
  72. extern struct set  *eclosure();          /* Used only by DFA */
  73. extern struct move *stbase();           /* Used only by DFA */
  74. extern struct dfa  *newdfa();  /* --> current DFA state */
  75. extern struct dfa  *defalt();            /* Used only by DFA */
  76. extern struct xset *addxset();
  77. extern struct xset *addset();
  78. extern char        *lalloc();
  79. extern void        add();
  80. extern void        error();
  81. extern void        f_error();  /* Fatal error */
  82. extern void        setbase();
  83. #endif
  84.  
  85.  
  86.  
  87. /*
  88.  * Build the DFA from the NFA
  89.  */
  90. PAGE( DFABUILD )
  91.  
  92. void dfabuild()
  93. {
  94.     struct trans *trp;
  95.     struct nfa **vec, **tp, *np, *temp[MAXNFA+1];
  96.     int a, i;
  97.     struct set *sp, *stack[MAXDFA], **spp, *xp, *tset;  /* DFA set stack */
  98.     struct dfa *state;    /* --> current DFA state */
  99.     struct xset *xs, *xse;
  100.  
  101.   /*
  102.    * Simulate an epsilon transition from nfa state 0 to
  103.    * the initial states of the machines for each
  104.    * translation.
  105.    */
  106.     nfa[0].n_char = EPSILON;    /* Set NFA state 0 transition EPSILON */
  107.  
  108.     /*
  109.     * Allocate a state vector, each node of which will
  110.     * point to an NFA starting state.  Each translation
  111.     * generates an NFA, so the number of translations
  112.     * equals the number of NFA start states.
  113.     */
  114.  
  115.     i = (transp - trans);  /* transp is updated in newtrans(); */
  116. #ifdef DEBUG
  117.     fprintf(stdout, "\nThe number of i states is: %d\nThe size is: %d\n", i, sizeof(struct nfa *) );
  118. #endif
  119.     i++;
  120.     /* Allocate "vec" for i states */
  121.     vec = (struct nfa **)lalloc( (unsigned)i, sizeof(struct nfa *), "dfabuild");
  122.  
  123.     /*
  124.     * Fill in the start state vector
  125.     */
  126.  
  127.     vec[0] = &nfa[0];               /* vec[0] always --> NFA state 0 */
  128.  
  129.     for (a = 1, trp = &trans[0]; trp < transp; trp++)  /* For each translation */
  130.     {
  131.        assert( isdata( (char *)trp->t_start, sizeof( struct nfa )));
  132.        vec[a++] = trp->t_start;         /* Pick up the NFA start state */
  133.     }
  134. #ifdef DEBUG
  135.     fprintf(stdout, "\nDFA: line 80" );
  136. #endif
  137.  
  138.     /*
  139.     * Now build the set sp --> e-CLOSURE(vec)
  140.     *    Seperated newset & ecl nesting to isolated failure mode.
  141.     */
  142.     tset = newset( vec, i, 1 );
  143.  
  144. #ifdef DEBUG
  145.     fprintf(stdout, "\nDFA: line 90 -- Prior to eclosure call" );
  146. #endif
  147.  
  148.     sp = eclosure( tset );
  149. #ifdef DEBUG
  150.     assert( isdata( (char *)sp, sizeof(struct set) ) );
  151. #endif
  152.  
  153.     /* Deallocate the start state vector */
  154.     assert( isdptr( (char *)vec ) );
  155.     if(free( (char *)vec) != 0)
  156.     {
  157.         f_error("\nDFA: Error is the release of v","");
  158.     }
  159.  
  160.     /*
  161.     * At this point state 0 of the DFA is constructed.
  162.     * This is the start state of the DFA.
  163.     * Mark it "added" and push it on to the stack.
  164.     */
  165. #ifdef DEBUG
  166.     fprintf(stdout, "\nDFA: line 111 -- build the dfa stack" );
  167. #endif
  168.     sp->s_flag |= ADDED;
  169.     spp = stack;
  170.     *spp++ = sp;
  171.  
  172.     /*
  173.     * From state 0, which is now stacked, all further DFA
  174.     * states will be derived.
  175.     */
  176.  
  177.     while(spp > stack)
  178.     {
  179.        sp = *--spp;
  180.        for(a = 0; a < NCHARS; a++) insets[a] = '\0';
  181.  
  182.        xse = &sets[0];
  183.        for (i = 0; i < sp->s_len; i++)
  184.        {
  185. #ifdef DEBUG
  186.            fprintf( stdout,"\nADDSET LOOP: count = %d", i);
  187.            fprintf( stdout,"\nADDSET LOOP: offset= %d", sp->s_els[i] - &nfa[0]);
  188.            tmp11 = sp->s_els[i];
  189.            if( tmp11 != NULL )
  190.                 assert( isdata( (char *)tmp11, sizeof( long ) ) );
  191. #endif
  192.            xse = addset(sp->s_els[i], xse);
  193.        }
  194.  
  195.        sp->s_state = state = newdfa();
  196.        state->df_name = sp;
  197.  
  198. #ifdef DEBUG
  199.        fprintf( stdout, "\nbuild state %d ", state - dfa);
  200.        fprintf( stdout, "\n" );
  201. #endif
  202.  
  203.        state->df_ntrans = xse - sets;
  204.        for(xs = sets; xs < xse; xs++)
  205.        {
  206.            a = xs->x_char & CMASK;
  207.            tp = temp;
  208.            for(i = 0; i < sp->s_len; i++)
  209.            {
  210.                if(
  211.                    (np = sp->s_els[i])->n_char == a ||
  212.                    np->n_char == CCL &&
  213.                    ( np->n_ccl[a/NBPC] & ( 1 << (a%NBPC) ) )
  214.                 )
  215.                    add( temp, &tp, np->n_succ[0] );
  216.            }
  217. #ifdef DEBUG
  218.     fprintf(stdout, "\nDFA: line 137 -- Prior to NEWSET call" );
  219. #endif
  220.  
  221.            xp = newset((struct nfa **)temp, (int)(tp- temp), 1 );
  222.  
  223. #ifdef DEBUG
  224.     fprintf(stdout, "\nDFA: line 141 -- Post NEWSET call" );
  225.     assert( isdata( (char *)xp, sizeof( struct set) ) );
  226. #endif
  227.  
  228.            xp = eclosure(xp);
  229.  
  230. #ifdef DEBUG
  231.            putc('\t',stdout);
  232.            chprint( a );
  233.            putc('\t', stdout);
  234.            fprintf( stdout, "\n");
  235. #endif
  236.  
  237.            xs->x_set = xp;
  238.            if(xp->s_state == NULL && (xp->s_flag & ADDED)==0)
  239.            {
  240.                xp->s_flag |= ADDED;
  241.                if(spp >= &stack[MAXDFA]) /* AMW: modified to use '&' */
  242.                {
  243.                    f_error("dfabuild: stack overflow","");
  244.                }
  245.                *spp++ = xp;
  246.            }
  247.        }
  248.  
  249.        /* the sub DEFALT() is in BASE.C */
  250. #ifdef DEBUG
  251.     fprintf(stdout, "\nDFA: line 165 -- prior to calling defalt, stbase, etc." );
  252. #endif
  253.        state->df_default = defalt(state, &xse);
  254.  
  255.        /* the following subs are in BASE.C */
  256.        setbase(state, stbase(xse), xse);
  257.     }
  258. }
  259.  
  260. PAGE( ADD )
  261. /*
  262.  * If an nfa state is not already a member of the vector `base', add it.
  263.  */
  264.  
  265. void add(base, tpp, np)
  266. st